Supporting Soft Real-Time Sporadic Task Systems on Heterogeneous Multiprocessors with No Utilization Loss

摘要

Heterogeneous multicore architectures are becoming increasingly popular dueto their potential of achieving high performance and energy efficiency comparedto the homogeneous multicore architectures. In such systems, the real-timescheduling problem becomes more challenging in that processors have differentspeeds. A job executing on a processor with speed $x$ for $t$ time unitscompletes $(x \cdot t)$ units of execution. Prior research on heterogeneousmultiprocessor real-time scheduling has focused on hard real-time systems,where, significant processing capacity may have to be sacrificed in theworst-case to ensure that all deadlines are met. As meeting hard deadlines isoverkill for many soft real-time systems in practice, this paper shows that onsoft real-time heterogeneous multiprocessors, bounded response times can beensured for globally-scheduled sporadic task systems with no utilization loss.A GEDF-based scheduling algorithm, namely GEDF-H, is presented and responsetime bounds are established under both preemptive and non-preemptive GEDF-Hscheduling. Extensive experiments show that the magnitude of the derivedresponse time bound is reasonable, often smaller than three task periods. Tothe best of our knowledge, this paper is the first to show that soft real-timesporadic task systems can be supported on heterogeneous multiprocessors withoututilization loss, and with reasonable predicted response time.